Meta-Tunning 1

컴파일러는 복사 생략(copy elision)과 같은 범용적인 최적화 기법 외에도
루프 풀기(Loop Unrolling)과 같은 수치적 최적화 기법을 제공한다.

루프 풀기는 여러 번 반복하는 반복문을 한 번에 수행하도록 변환하는 기법을 의미한다.
루프 풀기를 통해서 반복문 제어의 오버헤드를 줄이고, 동시에 실행 가능성을 높인다.

대부분의 컴파일러는 안쪽에 있는 반복문에 대해서만, 루프 풀기를 적용하지만,
여러 반복문을 풀게 되면, 성능이 향상될 수 있다.

컴파일러는 많은 부분에서 컴파일을 수행하지만, 특수 사례의 수와 관계없이 항상 도메인별로
최적화 해주어야 한다.
고전적인 고정 크기 풀기(반복문 풀기)
가장 간단한 형태의 컴파일 타임 최적화는 고정된 크기의 데이터 타입에 적용할 수 있다.

제네릭 벡터 할당 연산자
template <typename T, int size>
class fsize_vector{
public:
const static int my_size=Size;
T* data;
// ...
template <typename Vector>
Vector& operator=(const Vector& that){
for(int i=0; i<my_size; ++i) data[i]=that[i];
}
};
위의 코드에서 반복문을 아래와 같이 풀어서 쓸 수 있다.
template <typename T, int size>
class fsize_vector{
public:
const static int my_size=Size;
T* data;
// ...
template <typename Vector>
Vector& operator=(const Vector& that){
data[0]=that[0];
data[1]=that[1];
data[2]=that[2];
// ...
}
};
위의 코드에서 템플릿 인수 Vector가 표현식 템플릿(Expression Template)일 수도 있다.
표현식 템플릿의 계산 또한 인라인해서 표현할 수 있다.
ex) ET; alpha*x+y

표현식 템플릿 내에서 fsize_vector를 friend라고 선언했다고 가정
template <typename T, int size>
class fsize_vector{
public:
const static int my_size=Size;
T* data;
// ...
template <typename Vector>
Vector& operator=(const Vector& that){
data[0]=alpha*that.x[0]+that.y[0];
data[1]=alpha*that.x[1]+that.y[1];
data[2]=alpha*that.x[2]+that.y[2];
// ...
}
};
메타 튜닝을 단계별로 도입하기 위한 펑터
template <typename Target, typename Source, int N>
struct fize_assign{
void operator()(Target& tar, const Source& src){
fsize_assign<Target, Source, N-1>()(tar, src);
std::cout<<"assign entry "<<N<<'\n';
tar[N]=src[N];
}
};
template <typename Target, typename Source>
struct fsize_assign<Target, Source, 0>{
void operator()(Target& tar, const Source& src){
std::cout<<"assign entry "<<0<<'\n';
tar[0]=src[0];
}
};
혹은
template <int N>
struct fsize_assign{
template <typename Target, typename Source>
void operator()(Target& tar, const Source& src){
fsize_assign<N-1>()(tar, src);
std::cout<<"assign entry "<<N<<'\n';
tar[N]=src[N];
}
};
template <>
struct fsize_assign<0>{
template <typename Target, typename Source>
void operator()(Target& tar, const Source& src){
std::cout<<"assign entry "<<0<<'\n';
tar[0]=src[0];
}
};
반복문 구현 대신, 연산자에서 재귀 할당 펑터(fsize_assign)를 호출하면 된다.
template <typename T, int Size>
class fsize_vector{
using self=fsize_vector;
// ...
static_assert(my_size>0, "Vector must be larger than 0");
self& operator=(const self& that){
fsize_assign<my_size-1>{}(*this, that);
return *this;
}
template <typename Vector>
self& operator=(const Vector& that){
fsize_assign<my_size-1>{}(*this, that);
return *this;
}
};
컴파일러가 반복문을 재귀로 바꿔 연산과 반복문 제어를 인라인한다.
위와 같은 기법은 L1 캐시에서 실행되는 작은 반복문에만 유용하다.

더 큰 반복문은 메모리의 데이터를 불러오면서 주는 영향이 크며, 반복문의 오버헤드는 무시할 수 있다.
매우 큰 벡터를 사용해 모든 연산을 풀게 되면, 명령어를 불러와야 하므로 성능이 저하된다.
중첩 풀기
대부분의 컴파일러는 중첩되지 않은 반복문을 푼다.
하지만, 사용자 정의 타입으로 인스턴스화된 많은 템플릿 인수가 있는 프로그램은 최적화를 할 수 없다.

행렬 벡터 곱셈을 사용한 컴파일 타임에 중첩 반복문 풀기(고정 크기를 갖는 행렬)
template <typename T, int Rows, int Cols>
class fsize_matrix{
static_assert(Rows>0, "Rows must be larger than 0");
static_assert(Cols>0, "Cols must be larger than 0");
using self=fsize_matrix;
public:
using value_type=T;
const static int my_rows=Rows, my_cols=Cols;
fsize_matrix(const self& that){ /* ... */ }
// 열 인덱스는 확인 구현 x
const T* operator[](int r) const { return data[r]; }
T* operator[](int r){ return data[r]; }
// 표현식 템플릿을 사용하여 구현(벡터 복사 동작을 피하기 위함)
mat_vec_et<self, fsize_vector<T, Cols>> operator*(const fsize_vector<T, Cols>& v) const {
return {*this, v};
}
private:
T data[Rows][Cols];
};
template <typename T, int Size>
class fsize_vector{
using self=fsize_vector;
// 표현식 템플릿 타입을 위한 벡터 할당 오버로드
template <typename Matrix, typename Vector>
self& operator=(const mat_vec_et<Matrix, Vector& that){
using et=mat_vec_et<Matrix, Vector>;
using mv=fsize_mat_vec_mult<et::my_rows-1, et::my_cols-1>;
mv{}(that.A, that.v, *this); // fsize_mat_vec_mult의 펑터 사용
return *this;
}
};
fsize_mat_vec_mult는 세 인수에 대한 행렬 벡터의 곱을 계산하는 템플릿 표현식이다.
template <int Rows, int Cols>
struct fsize_mat_vec_mult{
template <typename Matrix, typename VecIn, typename VecOut>
void operator()(const Matrix& A, const VecIn& v_in, VecOut& v_out){
fsize_mat_vec_mult<Rows, Cols-1>()(A, v_in, v_out);
v_out[Rows]+=A[Rows][Cols]*v_in[Cols];
}
};
// Cols=0을 위한 부분 특수화
template <int Rows>
struct fsize_mat_vec_mult<Rows, 0>{
template<typename Matrix, typename VecIn, typename VecOut>
void operator()(const Matrix& A, const VecIn& v_in, const VecOut v_out){
fsize_mat_vec_mult<Rows-1, Matrix::my_cols-1>()(A, v_in, v_out);
v_out[Rows]=A[Rows][0]*v_in[0];
}
};
// 재귀 종료를 위한 전체 특수화
template <>
struct fsize_mat_vec_mult<0, 0>{
template <typename Matrix, typename VecIn, typename VecOut>
void operator()(const Matrix& A, const VecIn& v_in, VecOut& v_out){
v_out[0]=A[0][0]*v_in[0];
}
};
인라인을 통한 프로그램은 벡터의 크기가 4인 경우, w=A*v는 아래와 같이 실행된다.
w[0]=A[0][0]*v[0];
w[0]+=A[0][1]*v[1];
w[0]+=A[0][2]*v[2];
w[0]+=A[0][3]*v[3];
w[1]=A[1][0]*v[0];
w[1]+=A[1][1]*v[1];
w[1]+=A[1][2]*v[2];
…
동시성 증가시키기
위 코드에서 대상 벡터의 항목에 대한 모든 작업을 한 번 훑으면서(loop) 수행된다는 점이다.
따라서 두 번째 작업을 위해서 첫 번째 작업을 기다려야 하고, 세 번째 작업을 위해서 두 번째 작업을 기다려야 한다.
동시성이 매우 제한된다.

w[0]=A[0][0]*v[0]
w[1]=A[1][0]*v[0];
w[2]=A[2][0]*v[0];
w[3]=A[3][0]*v[0];
w[0]+=A[0][1]*v[1];
w[1]+=A[1][1]*v[1];
…
위 처럼 안쪽 반복문에서 결과 벡터와 행렬의 행을 탐색할 때, 더 많은 동시성을 제공한다.
template <typename Rows, int Cols>
struct fsize_mat_vec_mult_cm{
template <typename Matrix, typename VecIn, typename VecOut>
void operator()(const Matrix& A, const VecIn& v_in, VecOut& v_out){
f_size_mat_vec_mult_cm<Rows-1, Cols>()(A, v_in, v_out);
v_out[Rows]+=A[Rows][Cols]*v_in[Cols];
}
};
template <int Cols>
struct fsize_mat_vec_mult_cm<0, Cols>{
template <typename Matrix, typename VecIn, typename VecOut>
void operator()(const Matrix& A, const VecIn& v_in, VecOut& v_out){
fsize_mat_vec_mult_cm<Matrix::my_rows-1, Cols-1>()(A, v_in, v_out);
v_out[0]+=A[0][Cols]*v_in[Cols];
}
};
template <int Rows>
struct fsize_mat_vec_mult_cm<Rows, 0>{
template <typename Matrix, typename VecIn, typename VecOut>
void operator()(const Matrix& A, const VecIn& v_in, VecOut& v_out){
fsize_mat_vec_multi_cm<Rows-1, 0>()(A, v_in, v_out);
v_out[Rows]=A[Rows][0]+v_in[0];
}
};
template <>
struct fsize_mat_vec_mult_cm<0, 0>: fsize_mat_vec_mult<0, 0> {};
SIMD(Single Instruction Multiple Data)
위는 동일한 연산을 연산을 수행하지만, 이익을 얻을 수 있다.

최신 프로세서에는 여러 부동소수점 수에서 동시에 산술 연산을 수행하는 SSE 장치가 포함되어 있다.
SSE 명령을 사용하기 위해서는 처리된 데이터가 메모리에서 정렬되고 연속적이어야 하며, 컴파일러가 이를 인식해야 한다.

코드를 풀면 동일한 작업이 인접한 메모리에서 실행되게 할 수 있다.
레지스터 사용하기(register)
모던 프로세서의 특징에서 캐시 일관성에 염두해 두어야 한다.
(오늘날 프로세서는 캐시의 일관성을 유지하면서 메모리를 공유하도록 설계됨)

벡터 w를 메모리에 자료 구조를 작성할 때마다, 캐시 무효화 시그널을 다른 코어 및 프로세서로 전송한다.
이는 계산을 느려지게 한다.

캐시 무효화 병목 현상은 대부분의 경우 타입을 허용할 때, 레지스터에 있는 함수에 임시 변수를 도입해 피할 수 있다.

C++03에서 register 키워드가 있었다.
register 키워드는 단순한 힌트로 컴파일러는 변수를 레지스터에 저장해야 할 의무는 없다.
따라서 C++11에서는 register 키워드를 더 이상 사용하지 않음
template <int Rows, int Cols>
struct fsize_mat_vec_mult_reg{
template <typename Matrix, typename VecIn, typename VecOut>
void operator()(const Matrix& A, const VecIn& v_in, VecOut& v_out){
fsize_mat_vec_mult_reg<Rows-1, Cols>()(A, v_in, v_out);
// 최신 컴파일러는 아래의 tmp를 레지스터에 할당할 것임
typename VecOut::value_type tmp;
fsize_mat_vec_mult_aux<Rows, COls>()(A, v_in, tmp);
v_out[Rows]=tmp;
}
};
template <int Cols>
struct fsize_mat_vec_mult_reg<0, Cols>{
template <typename Matrix, typename VecIn, typename VecOut>
void operator()(const Matrix& A, const VecIn& v_in, VecOut& v_out){
// 최신 컴파일러는 아래의 tmp를 레지스터에 할당할 것임
typename VecOut::value_type tmp;
fsize_mat_vec_mult_aux<0, Cols>()(A, v_in, tmp);
v_out[0]=tmp;
}
};
template <int Rows, int Cols>
struct fsize_mat_vec_mult_aux{
template <typename Matrix, typename VecIn, typename ScalOut>
void operator()(const Matrix& A, const VecIn& v_in, ScalOut& tmp){
fsize_mat_vec_mult_aux<Row, Cols-1>()(A, v_in, tmp);
tmp+=A[Rows][Cols]*v_in[Cols];
}
};
template <int Rows>
struct fsize_mat_vec_mult_aux<Rows, 0>{
template <typename Matrix, typename VecIn, typename ScalOut>
void operator()(const Matrix& A, const VecIn& v_in, ScalOut& tmp){
tmp=A[Rows][0]*v_in[0];
}
};
이 외에도 캐시 무효화 시그널을 더욱 최소화하는 라이트 백(write-back)을 집적(agglometration) 시키는 최적화 기법도 있다.